#include "tree.h"

/*****核心功能函数*****/
bool isequal(cstree t1, cstree t2)
{
    /***两棵树均非空***/
    while (t1 != nullptr && t2 != nullptr)
    {
        /*发现不相同的结点，或者不相同的左子树，直接返回false*/
        if (t1->data != t2->data || isequal(t1->leftmostchild, t2->leftmostchild) == false)
        {
            return false;
        }

        /*2个游动指针指向根结点的右兄弟结点*/
        else
        {
            t1 = t1->rightsibling;
            t2 = t2->rightsibling;
        }
    }

    /***如果2棵树相等，则一定会运行到循环结束，而且此时2个游动指针一定全部是nullptr***/
    if (t1 == nullptr && t2 == nullptr)
    {
        return true;
    }

    /***如果2棵树不相等，那么一定有1个游动指针不为空，对应的二叉树没遍历完，2棵树不相等***/
    return false;
   
}
/*****核心功能函数*****/

/*****主函数*****/
int main()
{
    t0 = nullptr;
    t1 = (cstree)malloc(sizeof(cstnode));
    t2 = (cstree)malloc(sizeof(cstnode));
    t3 = (cstree)malloc(sizeof(cstnode));
    t4 = (cstree)malloc(sizeof(cstnode));
    t5 = (cstree)malloc(sizeof(cstnode));
    t6 = (cstree)malloc(sizeof(cstnode));
    t7 = (cstree)malloc(sizeof(cstnode));
    t8 = (cstree)malloc(sizeof(cstnode));
    t9 = (cstree)malloc(sizeof(cstnode));
    t10 = (cstree)malloc(sizeof(cstnode));
    t_init();

    /***第1组树：2棵空树***/
    printf("*****第1组树*****\n");
    t0 = nullptr;
    t1 = nullptr;
    printf("第1棵树：\n");
    print_t(t0);
    printf("\n第2棵树：\n");
    print_t(t1);
    printf("\n比较结果：");
    if (isequal(t0, t1))
    {
        printf("这2棵树相同。\n");
    }
    else
    {
        printf("这2棵树不同。\n");
    }
    
    t1 = (cstree)malloc(sizeof(cstnode)); // t1之前已经变成nullptr了，必须重新分配内存空间，否则会出现segmentation fault
    t_init();
    printf("*****第1组树*****\n\n\n\n");
    /***第1组树：2棵空树***/

    /***第2组树：1棵空树，1棵非空树***/
    printf("*****第2组树*****\n");
    t0 = nullptr;
    t1->leftmostchild = t2;
    t1->rightsibling = t3;
    t2->rightsibling = t4;
    t4->leftmostchild = t5;
    printf("第1棵树：\n");
    print_t(t0);
    printf("\n第2棵树：\n");
    print_t(t1);
    printf("\n比较结果：");
    if (isequal(t0, t1))
    {
        printf("这2棵树相同。\n");
    }
    else
    {
        printf("这2棵树不同。\n");
    }
    printf("*****第2组树*****\n\n\n\n");

    t_init();
    /***第2组树：1棵空树，1棵非空树***/

    /***第3组树：2棵非空树***/
    printf("*****第3组树*****\n");
    t0 = nullptr;
    t1->leftmostchild = t2;
    t1->rightsibling = t3;
    t2->rightsibling = t4;
    t4->leftmostchild = t5;
    t6->leftmostchild = t7;
    t6->rightsibling = t8;
    t7->rightsibling = t9;
    t9->leftmostchild = t10;
    printf("第1棵树：\n");
    print_t(t1);
    printf("\n第2棵树：\n");
    print_t(t6);
    printf("\n比较结果：");
    if (isequal(t1, t6))
    {
        printf("这2棵树相同。\n");
    }
    else
    {
        printf("这2棵树不同。\n");
    }
    printf("*****第3组树*****\n\n\n\n");

    t_init();
    /***第3组树：2棵非空树***/

    /***第4组树：2棵非空树***/
    printf("*****第4组树*****\n");
    t0 = nullptr;
    t1->leftmostchild = t2;
    t2->rightsibling = t4;
    t4->leftmostchild = t5;
    t4->rightsibling = t3;
    t6->leftmostchild = t7;
    t6->rightsibling = t8;
    t7->rightsibling = t9;
    t9->leftmostchild = t10;
    printf("第1棵树：\n");
    print_t(t1);
    printf("\n第2棵树：\n");
    print_t(t6);
    printf("\n比较结果：");
    if (isequal(t1, t6))
    {
        printf("这2棵树相同。\n");
    }
    else
    {
        printf("这2棵树不同。\n");
    }
    printf("*****第4组树*****\n\n\n\n");

    t_init();
    /***第4组树：2棵非空树***/

    /***第5组树：2棵非空树（结构相同）***/
    printf("*****第5组树*****\n");
    t0 = nullptr;
    t1->data = '0';
    t1->leftmostchild = t2;
    t1->rightsibling = t3;
    t2->rightsibling = t4;
    t4->leftmostchild = t5;
    t6->leftmostchild = t7;
    t6->rightsibling = t8;
    t7->rightsibling = t9;
    t9->leftmostchild = t10;
    printf("第1棵树：\n");
    print_t(t1);
    printf("\n第2棵树：\n");
    print_t(t6);
    printf("\n比较结果：");
    if (isequal(t1, t6))
    {
        printf("这2棵树相同。\n");
    }
    else
    {
        printf("这2棵树不同。\n");
    }
    printf("*****第5组树*****\n\n\n\n");

    t_init();
    /***第5组树：2棵非空树（结构相同）***/

    system("pause");
}
/*****主函数*****/